/*
Source : https://leetcode.com/problems/reverse-integer/
Author : nflush@outlook.com
Date   : 2016-05-19
*/
/*
214. Shortest Palindrome
Total Accepted: 19865 Total Submissions: 99668 Difficulty: Hard

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Thanks to @Freezen for additional test cases.

Subscribe to see which companies asked this question
*/
class Solution {
public:
    string shortestPalindrome(string s) {
        int len = s.size();
        if(len <= 1) return s;
        
        string pattern = s + '\0' + string(s.rbegin(), s.rend());  

        //construct the partial match table
        vector<int> prefix( pattern.size() );  
        prefix[0] = 0;
        for(int i = 1; i < prefix.size(); i++) {  
            int j = prefix[i-1];  
            while( j > 0 && pattern[i] != pattern[j] ) {
                j = prefix[j-1];  
            }
            if ( pattern[i] == pattern[j] ) {
                j++;  
            }
            prefix[i] = j;  
        }  
        int pos = s.size() - prefix.back();  
        return string(s.rbegin(), s.rbegin() + pos) + s;  
    }
};

char* shortestPalindrome(char* s) {
    
}

